Data compression schemes are widely used today in computer systems. These data compression schemes are comprised of stages coupled together to provide compression or decompression. The stages may include cascaded arrangements of data compression schemes. For example, the Joint Photographic Experts Group (JPEG) Still Image Compression Standard transforms the data with a two dimensional discrete cosine transform and then the coefficients are quantized. This is followed by differential pulse code modulation (DPCM) of the DC coefficients and run-length encoding of the AC coefficients. Finally, the results are Huffman coded. Since the decompression portion of a data compression system is the inverse of the compression portion, decoders are cascaded into consecutive stages as well.
Some data compression techniques are lossy. In a lossy compression technique, a portion of the input data is eliminated or quantized during compression, such that the compressed data cannot be decompressed into an exact duplicate of the input data. Lossy image compression is often accomplished using multiple stages. An example of such a system is shown in FIG. 1.
Sometimes these cascaded stages run at different rates. For real-time systems with cascaded asynchronous stages, buffering the data becomes a major design issue. Referring to FIG. 1, lossy compressor 101 receives data input 110 at a rate R. In one embodiment, lossy compressor 101 may be a transform code (TC) compressor that produces coefficients in response to the input data 110 at a set rate of R. The output of lossy compressor 101 is coupled to the input of run-length encoder (RLE) 102. Run-length encoder 102 receives and compresses the output from lossy compressor 101 at rate R. Run-length encoder 102 is a variable length encoder and produces tokens at an average, but not constant, rate of R-G in response to its input. The tokens output from run-length encoder 102 are coupled to the input of coder 103 which encodes the received tokens into codewords. These codewords are produced at an average rate of R-G. The codewords are then stored or transmitted on a channel.
Decompression of a compressed data stream using the system in FIG. 1 is very similar to the compression, with the exception that the stages are reversed. Decoder 106 receives the compressed data stream and produces tokens at an average, but not constant, rate R-G. The tokens are received by run-length encoder 105 which produces coefficients at a rate R. The coefficients are received by lossy decompressor 104 which produces a reconstructed data input 111.
As described, the stages in the lossy image compression system run at different rates. The rates of the stages are R and R-G, where R&gt;G.gtoreq.0. This is mainly due to the variable length coding (i.e., run-length encoder/decoder). If in this example, the coder and decoder can run at rate R, there is no problem since the stages can be operated synchronously. Otherwise, buffering is necessary to average the rate of the coder and decoder.
In the prior art, if a slower stage is incapable of operating at least in a burst rate R, a first-in/first-out (FIFO) buffer may be used. A FIFO buffer is a well-known asynchronous solution to interfacing between stages that operate at different rates. The FIFO buffer allows a preceding faster stage to operate at its maximum rate until the FIFO is full. The FIFO buffer essentially averages the rates of output codes.
The size of the necessary FIFO buffer depends on how long averaging is to occur. In other words, the size of the FIFO buffer determines the window of averaging. If the FIFO size is the size of the image, then the FIFO can accommodate all burst rates. However, the larger the size of the buffer, the larger the cost. Moreover, the increased size generally brings about a diminished return due to the minimal number of situations that are accommodated by the added size of the buffer.
Also, encoders and decoders are often implemented in application specific integrated circuits (ASICs). When a buffer is required, the buffer may be included in the same integrated circuit chip as the decoder. The size of the memory is directly related to the overall size of the chip. The larger the size of the buffer, the larger the size of the integrated circuit. Larger integrated circuits typically cost more. In order to keep the chip size reduced, thereby reducing the overall cost of the chip, it is desirable to reduce the buffer to the smallest size possible. Therefore, it is desirable to reduce the size of the buffer storage required to effectively reduce the cost of the system.
The present invention provides a method and apparatus for reducing the size of a buffer in a lossy data compression system. The present invention reduces the size of the buffer used between multiple stages in the decompression.